package org.datastructure.secondday.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Graph {
    private List<String> vertexList;
    private boolean[] isVisited;
    private int[][] edges;


    public Graph(int n) {
        vertexList = new ArrayList<>(n);
        edges = new int[n][n];
    }


    public static void main(String[] args) {
       // String Vertexs[] = {"A", "B", "C", "D", "E"};
        String Vertexs[] = {"1", "2", "3", "4", "5", "6", "7", "8"};

        //测试一把图是否创建ok
        int n = Vertexs.length;  //结点的个数
        //创建图对象
        Graph graph = new Graph(n);
        //循环的添加顶点
        for (String vertex : Vertexs) {
            graph.insertVertex(vertex);
        }
        //添加边
        //A-B A-C B-C B-D B-E
       /* graph.insertEdge(0, 1, 1); // A-B
        graph.insertEdge(0, 2, 1); //
        graph.insertEdge(1, 2, 1); //
        graph.insertEdge(1, 3, 1); //
        graph.insertEdge(1, 4, 1); //*/


        //更新边的关系
        graph.insertEdge(0, 1, 1);
        graph.insertEdge(0, 2, 1);
        graph.insertEdge(1, 3, 1);
        graph.insertEdge(1, 4, 1);
        graph.insertEdge(3, 7, 1);
        graph.insertEdge(4, 7, 1);
        graph.insertEdge(2, 5, 1);
        graph.insertEdge(2, 6, 1);
        graph.insertEdge(5, 6, 1);

        //显示一把邻结矩阵
        graph.showGraph();

        //测试一把，我们的dfs遍历是否ok
        System.out.println("深度遍历");
        graph.dfs(); // A->B->C->D->E [1->2->4->8->5->3->6->7]


        System.out.println("广度遍历");
        graph.bfs();

    }

    public void bfs() {
        isVisited = new boolean[vertexList.size()];
        for (int i = 0; i < vertexList.size(); i++) {
            if (!isVisited[i]) {
                bfs(isVisited, i);
            }
        }
    }

    public void bfs(boolean[] isVisited, int index) {

        int u, w;
        LinkedList<Integer> queue = new LinkedList<>();
        queue.add(index);
        isVisited[index] = true;
        System.out.println(vertexList.get(index) + "==>");
        while (!queue.isEmpty()) {

            u = queue.removeFirst();
            w = getFirstNeighbor(u);

            while (w != -1) {
                if (!isVisited[w]) {
                    System.out.println(vertexList.get(w) + "==>");
                    queue.add(w);
                    isVisited[w] = true;
                }
                w = getNextNeiphbor(u, w);
            }
        }
    }


    public void dfs() {
        isVisited = new boolean[vertexList.size()];
        // TODO: 2022/4/1  这里时为了非连接图时，不连接顶点无法遍历到 
        for (int i = 0; i < vertexList.size(); i++) {
            if (!isVisited[i]) {
                dfs(isVisited, i);
            }
        }
    }

    public void dfs(boolean[] isVisited, int index) {
        System.out.println(vertexList.get(index) + "==>");
        int w = getFirstNeighbor(index);
        isVisited[index] = true;
        while (w != -1) {

            if (!isVisited[w]) {
                dfs(isVisited, w);
            }
            w = getNextNeiphbor(index, w);
        }
    }

    public void showGraph() {
        for (int i = 0; i < vertexList.size(); i++) {
            System.out.println(Arrays.toString(edges[i]));
        }
    }

    public void insertVertex(String vertex) {
        vertexList.add(vertex);
    }


    public void insertEdge(int v, int h, int weight) {
        edges[v][h] = weight;
        edges[h][v] = weight;
    }


    /**
     * 获取邻接节点
     * 从第一个下标0开始找，和他相邻的第一个顶点
     *
     * @param index
     * @return
     */
    public int getFirstNeighbor(int index) {
        for (int i = 0; i < vertexList.size(); i++) {
            if (edges[index][i] > 0) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 获取邻接节点
     *
     * @param v1
     * @param v2
     * @return
     */
    public int getNextNeiphbor(int v1, int v2) {
        for (int i = v2 + 1; i < vertexList.size(); i++) {
            if (edges[v1][i] > 0) {
                return i;
            }
        }
        return -1;
    }
}
